1. The Field of the Invention
The present invention generally relates to image analysis techniques and more particularly relates to a method and apparatus for tracing connectivity in a mosaic of images.
2. The Relevant Technology
When analyzing objects using high magnification imaging techniques it is often the case where the area of interest for analysis exceeds the field of view of the imaging device. In such a situation, the area of interest is imaged in a so-called step-and-repeat fashion, whereby multiple images are acquired in a grid pattern that is organized as a series of rows and columns with intentional overlap between adjacent images. The images are then arranged to produce a composite or mosaic of the area of interest.
The analysis of integrated circuits (IC's) is a particular case where a mosaic of high magnification images may be required for purposes including reverse engineering, circuit analysis or quality control. As IC's generally include multiple layers of interconnected circuitry, such a mosaic of the entire circuit would require images from each layer of the IC. A single large image or model is then assembled by stitching together adjacent images of the mosaic using translational and/or rotational movements thereof. This model can generally have either two or three dimensions, where a two-dimensional (2D) model is constructed from mosaics from a single level within the IC, and where a three-dimensional (3D) model is constructed from mosaics from different levels within the IC.
Numerous techniques have been developed for the generation of a 2D/3D model from a mosaic. If one is given a pair of images with overlap between them, it is typically possible to stitch them together using a procedure called pair-wise registration, which is a well-known technique in the art. Pair-wise registration is used to digitally stitch together the images on a common plane by minimizing registration errors. Pair-wise registration accomplishes this through calculation of the relative image coordinates of a pair of images, and the selection of a single pair of corresponding points between the two images. More images may be pair-wise registered by applying a similar technique to another image and the previously registered image pair. Such a registration can be performed by techniques described in the paper “A survey of image registration techniques” by L. Brown, ACM Computing Surveys, Vol. 24, Issue 4, 1992, incorporated by reference herein.
However, there are drawbacks in using the above-noted techniques when there are more than three images in the mosaic. If, for example, there are four images, e.g., images 1 through 4, with each image located in the corner of a square, there are four overlap areas that need to be aligned. One might ideally stitch the seams of image pairs (1,2) and (1,3) using translation only. However, by so doing, it would not be possible to stitch seams (2,4) and (3,4). Depending on the position of image 4, generally only one of image pairs (2,4) and (3,4) can be aligned without errors. If only one pair can be aligned, a bundle adjustment procedure may be performed to find an acceptable distribution of error, such that the error in each overlap area is within a certain tolerable range.
Briefly, bundle adjustment procedures implement energy minimization techniques to select appropriate transformations of images where overall (e.g., sum or maximum) alignment error is minimized globally for all overlap areas. In the simplest form, for 2 dimensional grids where only image movement in the X and Y directions is allowed, a simple least squares procedure can be used.
Bundle adjustment techniques can be implemented, not only for the production of a model, but they can also be used to detect an overlap region in which the alignment information introduces excessive errors to the model. An implementation of bundle adjustment techniques can be found in the applicant's co-pending U.S. patent application publication no. 2006/0257051, disclosed by Vyacheslav Zavadsky et al.
While most of the literature on bundle adjustment deals with the more complicated problem of producing a 2D/3D model in the case of a moving camera, the same methods can be applied to producing global stitching of an image mosaic after mathematical reduction to the model as described in, for example, B. Triggs, P. McLauchlan, R. Hartley, and A. Fitzgibbon, “Bundle Adjustment—A Modern Synthesis” in B. Triggs, A. Zisserman, and R. Szeliski, Vision Algorithms: Theory & Practice (Springer-Verlag, 2000).
A further complication in stitching images together arises when the pair of images depicts objects in a highly repetitive area, such as, for example, within a memory array. In this case, distinctive features may be too small or masked by overall noise.
In cases where the imaging of 3D objects is performed while either the object or the camera is moving, modeling may require running a complicated stereovision algorithm to form a 3D model of the stitched object. However, it will be apparent to the skilled artisan that the computational requirements for model building can become very large. For ICs, the minimum feature size is continually decreasing due to advances in the manufacturing processes. These decreases in turn increase the number of images that have to be aligned to produce the required 2D/3D model. As such, the computational resources required to produce a global 2D/3D model are becoming too large. Further, there is considerable overall implementation complexity, including factors to consider such as considerable research-level engineering, and familiarity with image processing, energy minimization (bundle adjustment), and robust statistics fields. Therefore, alternate methods of circuit analysis are quickly becoming important.
The discussion so far has considered the development of a 2D/3D model for a circuit. For an IC, there is a second stage of tracing connectivity that provides for signal continuity throughout the model. The various known techniques of the art have taken the approach that, first, a 2D/3D model of the IC is constructed, and then, second, connectivity is traced. The accuracy of the generated 2D/3D model will generally determine whether the connectivity tracing requires manual intervention, or if it can be advantageously performed in an automated fashion.
An exemplary prior art method is presented in FIG. 1. Overall, the method 100 provides a 2D or 3D model of aligned images and then traces connectivity through the overall model. At step 102, objects are detected for each image. The cycle 103 repeats step 102 until objects are detected for all images. After completing the cycle 103, step 106 is followed to produce a combined 2D or 3D model of all aligned images. Next, a combined model of the objects according to the combined 2D/3D model of aligned images is produced at step 108. As a final step, any connectivity between the objects is traced at step 110.
Although most implementations of the method 100 perform step 102 independently for each image, object detection can alternatively be performed on an aligned model that is produced at step 106. In this case, step 102 and cycle 103 would be combined into a step of detecting objects in the aligned model produced at step 106.
There are also variations on how step 106 is implemented in the art. In FIG. 2, a prior art method 200 of producing a 2D or 3D model is shown as an alternative for implementing step 106. A pair-wise alignment of an overlapped image pair is performed at step 206. Step 206 is repeated through cycle 207 for each overlapping pair of images. At step 208, a bundle adjustment is performed for alignment correction purposes. The method 200 is repeated at through cycle 209 for each image mosaic. Once the images are aligned, the points of alignment between each mosaic are determined at step 212. This is repeated through cycle 213 for each pair of overlapping mosaics. A 2D or 3D model is produced at step 214 and connectivity is traced at 216.
In published U.S. Patent application publication no. 2005/0226521, disclosed by A. Lachance and Z. Blaxell, the portion of method 200 ending at step 209 is replaced by a step of producing a coarse alignment for each mosaic. Step 212, i.e., the step of finding points of alignment between overlapped mosaics is performed by matching the ends of wires to vias. As a result, each image in a given mosaic is moved according to average displacements found during matching. However, while the images are being moved for inter-layer displacement, the intra-layer mosaic may be broken.
U.S. Pat. No. 6,249,616, issued to Hashimoto, discloses a method of aligning a single image mosaic when the images thereof are taken from different positions/different angles, which would require 3D model. The patent discloses a simplification for a bundle adjustment model because of the challenges faced in the art to perform the bundle adjustment on the entire model. As such, approaches for simplifying the bundle adjustment models are considered. However, these approaches presumably increase the likelihood of alignment errors in the overlap areas. It also presents a method for aligning a single image mosaic when the images of the mosaic are taken from different positions/different angles. However, this approach requires the production of 3D model, which adds to the level of complexity in aligning images because a 3D model must first be produced.
A paper by M. Brown and D. G. Lowe, “Recognizing Panoramas” Proceedings of the 9th International Conference on Computer Vision (ICCV2003) (Nice, France: October 2003), 1218, presents a method of aligning a single mosaic of images into panoramic view. Points of interest (Scale Invariant Feature Transform (SIFT) features) are detected, and then matched to each other based on pair-wise alignment. Spurious points of correspondence are deleted using the Random Sample Consensus (RANSAC) approach and the panorama is stitched using global bundle alignment. The author suggests that the method can be used for aligning multiple mosaics, however the bundle adjustment suggested produces some visible artifacts.
In applicant's co-pending U.S. patent application publication no. 2006/0257051, which is herein incorporated by reference, applicant discloses a method for providing an aligned 3D model of multiple mosaics as would be appropriate for automated connectivity tracing. This application teaches that step 206 (shown in FIG. 2) may be performed with template matching. The application also teaches additional methods to detect pairs with either ambiguous or no information. Furthermore, the application teaches that step 212 may be performed by either operators entering points of correspondence, or by matching vias to wires in the case of IC images. Finally, a global bundle adjustment least squares model is disclosed. The model allows the distribution of errors between inter- and intra-mosaic overlap. The main drawback is the complexity of the method.
As such, there is no known technique in the art that is capable of producing a combined 3D model of multi-mosaic images with precision sufficient for automated signal tracing.
As such, it would be advantageous to have a method of automating connectivity tracing in a manner that does not require the prior generation of a highly accurate 2D/3D model. Therefore, there is a need for a method that can perform automated connectivity tracing without forming a global 2D/3D model of the aligned mosaics. Furthermore, there is a need for a method of providing connectivity tracing that is independent of the scale of the IC.